package codeTop;

public class q143 {
    public void reorderList(ListNode head) {
        if (head==null||head.next==null||head.next.next==null) return;
        ListNode slow = head;
        ListNode fast = head;
        //让slow指针指向中间位置
        while (fast.next != null) {
            fast = fast.next.next==null?fast.next:fast.next.next;
            slow = slow.next;
        }
        //反转链表
        reverse(slow.next);
        slow.next = null;
        slow = head;
        while (fast != null) {
            ListNode temp = fast.next;
            //把fast插入到前面
            fast.next = slow.next;
            slow.next = fast;
            slow = fast.next;
            fast = temp;
        }
    }
    public void reverse(ListNode head){
        if (head==null) return;
        ListNode next = head.next;
        head.next = null;
        while (next != null) {
            ListNode temp = next.next;
            next.next = head;
            head = next;
            next = temp;
        }
    }

    public static void main(String[] args) {
        q143 q = new q143();
        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
        q.reorderList(node1);
    }
}
